// 1 1 2 3 5
// 暴力递归
function fib(n) {
    if (n === 1 || n === 2) {
        return 1
    }
    return fib(n-1) + fib(n-2)
}

console.time()
console.log(fib(30))
console.timeEnd()

// fib(3) = fib(2) + fib(1)


// 备忘录模式
function helper(arr, n) {
    if (n === 1 || n === 2) {
        return 1
    }
    // 已经计算过
    if (arr[n] !== 0) return arr[n]
    arr[n] = helper(arr, n - 1) + helper(arr,n - 2)
    return arr[n]
}

function fib2(n) {
    if (n < 1) return 0
    let arr = Array(n+1).fill(0)
    // 初始化最简情况
    return helper(arr, n)
}

console.time()
console.log(fib2(30))
console.timeEnd()

// dp数组解法
function fib3(n) {
    let dp = Array(n+1).fill(0)
    dp[1] = dp[2] = 1
    for(let i = 3;i <= n;i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}
console.time()
console.log(fib3(30))
console.timeEnd()

// 优化

function fib4(n) {
    if (n === 2 || n === 1) return 1
    let prev = 1,
        curr = 1
    for(let i = 3; i <= n;i ++) {
        let sum = prev + curr
        prev = curr
        curr = sum
    }
    return curr
}
console.time()
console.log(fib4(30))
console.timeEnd()
